package myself.a008CodingTest;

import java.util.Stack;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/25
 * Time 20:46
 * Mail 739153436@qq.com
 */
public class PalindromeList {
    // 笔试的时候使用，使用额外的容器
    public static boolean isPalindrome1(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 建立栈
        Node cur = head;
        Stack<Node> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 进行回文比较
        int size = stack.size();
        for (int i = 0; i < size / 2; i++) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // 面试的时候使用，不使用额外的容器
    // ![](http://img.yhzcmxq.cn/picgo/20210125205911.png)
    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node cur = head;
        Node last = null;

        boolean result = true;

        // 取中点
        /*Node slow = new Node(-1);
        slow.next = head;*/
        int mid = 0;
        Node quick = new Node(-1);
        quick.next = head;
        while (quick != null) {
            if (quick.next != null) {
                mid++;
//                slow = slow.next;
            }
            if (quick.next == null || quick.next.next == null) {
                break;
            }
            quick = quick.next.next;
        }

        // 链表指针改进
        int curIndex = 1;
        Node next = null;
        Node pre = null;
        while (cur != null) {
            if (curIndex < mid) {
                cur = cur.next;
            }
            if (curIndex == mid) {
                next = cur.next;
                cur.next = null;
                pre = cur;
                cur = next;
            }
            if (curIndex > mid) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            curIndex++;
        }
        last = pre;

        // 回文比较
        cur = head;
        while (cur != null) {
            if (last.value != cur.value) {
                result = false;
                break;
            }
            last = last.next;
            cur = cur.next;
        }

        // 链表还原
        cur = pre;
        pre = null;
        next = null;
        while (true) {
            if (cur.next == null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
                break;
            }
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return result;
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }
}
